import java.util.*;

public class TestBinaryTree {
    //静态内部类，不需要对象的调用，直接使用
    static class TreeNode{
        public char val;
        public TreeNode left; //存储左孩子的引用
        public TreeNode right; //存储右孩子的引用

        public TreeNode(char val){
            this.val = val;
        }
    }
    //创建树--返回这棵树的根节点
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;

        return A;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * Oj1 -- 144. 二叉树的前序遍历
     * @param root 根节点
     * @return 根节点值的 前序 遍历
     */
    public List<Character> preorderTraversal1(TreeNode root) { //法1
        List<Character> ret = new ArrayList<>();
        if(root == null){
            return ret;
        }
        ret.add(root.val);
        List<Character> leftTree = preorderTraversal1(root.left);  //leftTree接收左子树的根节点值
        ret.addAll(leftTree);

        List<Character> rightTree = preorderTraversal1(root.right); //rightTree接收右子树的根节点值
        ret.addAll(rightTree);

        return ret;
    }

    List<Character> ret = new ArrayList<>();
    public List<Character> preorderTraversal2(TreeNode root) { //法2
        if(root == null){
            return ret;
        }
        ret.add(root.val);
        preorderTraversal2(root.left);
        preorderTraversal2(root.right);
        return ret;
    }

    //非递归实现前序遍历
    public List<Character> preorderTraversal3(TreeNode root) { //法3
        List<Character> ret = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();

        while (cur != null || !stack.empty()){
            while (cur != null){
                stack.push(cur);
                System.out.println(cur.val +" ");
                ret.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop(); //如果左孩子为空，则出栈
            cur = top.right; //此时再判断右孩子节点
        }
        return ret;
    }

    // 中序遍历
    public void inOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    /**
     * Oj -- 94. 二叉树的中序遍历
     */
    List<Integer> ret1 = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) { //法1
        if(root == null){
            return ret1;
        }
        inorderTraversal(root.left);
        ret.add(root.val);
        inorderTraversal(root.right);
        return ret1;
    }
    public List<Character> inorderTraversal2(TreeNode root) { //法2
        List<Character> ret = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while(cur != null || !stack.empty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            ret.add(top.val);
            cur = top.right;
        }
        return ret;
    }

    // 后序遍历
    public void postOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

    /**
     * Oj -- 145. 二叉树的后序遍历
     */
    List<Integer> ret2 = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) { //法1
        if(root == null){
            return ret2;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        ret.add(root.val);
        return ret2;
    }

    public List<Character> postorderTraversal2(TreeNode root) { //法2
        List<Character> ret = new ArrayList<>();
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        while (cur != null || !stack.empty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev){ //难点
                ret.add(top.val);
                stack.pop();
                prev = top; //难点
            }else {
                cur = top.right;
            }
        }
        return ret;
    }

    /**
     *  获取树中节点的个数：遍历思路
     * @param root
     */
    public static int nodeSize = 0;
    public int size(TreeNode root) { // 法1
        if (root == null){
            return 0;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
        return nodeSize;
    }
    /** 法2：
     * 获取节点的个数：子问题的思路
     * @param root
     * @return
     */
    int size2(TreeNode root) { //法2
        if (root == null){
            return 0;
        }
        return size2(root.left) + size2(root.right) + 1; //所有的左子树节点+右子树节点+根节点（1）
    }


    /**
     * 获取叶子节点的个数：法1：遍历思路
     */
    public static int leafSize = 0;
    public int getLeafNodeCount1(TreeNode root) { //法1
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1; //叶子结点
        }
        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
    }

    /**
     获取叶子节点的个数：法2:子问题
     */
    int getLeafNodeCount2(TreeNode root) { //法2
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            leafSize++; //叶子结点
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
        return leafSize;
    }

    /**
     * 获取第K层节点的个数
     * 就是左树的 k-1层 + 右树的 k-1层
     */
    int getKLevelNodeCount(TreeNode root, int k) {
        if(root == null || k <= 0){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1);
    }

    /*
     获取二叉树的高度
     时间复杂度：O(N)
     */
    int getHeight(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }

    // 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode ret1 = find(root.left,val);
        if(ret1 != null){
            return ret1;
        }
        TreeNode ret2 = find(root.right,val);
        if(ret2 != null){
            return ret2;
        }
        return null;
    }

    //层序遍历
    public void levelOrder(TreeNode root) {
        if(root == null){
            return;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()){
            TreeNode cur = qu.poll();
            System.out.print(cur.val+" ");
            if(cur.left != null){
                qu.offer(cur.left);
            }
            if(cur.right != null){
                qu.offer(cur.right);
            }
        }
    }

    /** Oj2 -- 100. 相同的树
     *给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     *  如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null || q == null && p != null){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    /** Oj3------ 572. 另一棵树的子树
     *给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
     * 如果存在，返回 true ；否则，返回 false 。
     *二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null || subRoot == null){
            return false;
        }
        //1.判断两棵树 是不是两颗相同的树
        if(isSameTree(root, subRoot)){
            return true;
        }
        //2.subRoot是不是root.left的子树
        if(isSubtree(root.left, subRoot)){
            return true;
        }
        //3.subRoot是不是root.right的子树
        if(isSubtree(root.right, subRoot)){
            return true;
        }
        return false;
    }

    /** Oj4--  226. 翻转二叉树
     给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
     */
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return null;
        }
        // root不为空进行交换
        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;
        // 对左子树和右子树进行交换
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    /** Oj5 -- 110. 平衡二叉树
     *给定一个二叉树，判断它是否是高度平衡的二叉树。
     * 本题中，一棵高度平衡二叉树定义为：
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
     */
    public boolean isBalanced(TreeNode root) {
        //先判断当前root节点是否平衡，再看左子树是否平衡，看右子树是否平衡
        if(root == null){
            return true;
        }
        return getHeight2(root) >= 0;
    }

    //获取二叉树的高度
    int getHeight2(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(leftHeight >= 0 && rightHeight >= 0
                && Math.abs(leftHeight - rightHeight) <= 1){
            return Math.max(leftHeight, rightHeight) + 1;
        }else{
            return -1; //-1表示子树已经不平衡了
        }
    }

    /** Oj6 --  101. 对称二叉树
     给你一个二叉树的根节点 root ， 检查它是否轴对称。
     */
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.left, root.right);
    }

    private boolean isSymmetricChild(TreeNode leftTree, TreeNode rightTree){
        if(leftTree == null && rightTree != null ||
                leftTree != null && rightTree == null){
            return false;
        }
        if(leftTree == null && rightTree == null){
            return true;
        }
        if(leftTree.val != rightTree.val){
            return false;
        }
        //如果都不为空，就判断左树的左和右树的右，和左树的右和右树的左
        return isSymmetricChild(leftTree.left, rightTree.right) &&
                isSymmetricChild(leftTree.right, rightTree.left);
    }


    /** Oj 7 --- 102. 二叉树的层序遍历
     *给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）
     */
    public List<List<Character>> levelOrder2(TreeNode root) {
        List<List<Character>> list = new ArrayList<>();;
        //如何确定每一层
        if(root == null){
            return list;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);

        while (!qu.isEmpty()){
            int size = qu.size(); //确定每一层
            List<Character> tmp = new ArrayList<>(); //用于接收每一层的数据
            while (size > 0){
                TreeNode cur = qu.poll();
                size--;
                tmp.add(cur.val);
                if(cur.left != null){
                    qu.offer(cur.left);
                }
                if(cur.right != null){
                    qu.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }


    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()){
            TreeNode cur = qu.poll();
            if(cur != null){ //将它的左右子节点都存放在队列中（如果左右子节点为null也存放）
                qu.offer(cur.left);
                qu.offer(cur.right);
            }else {
                break; //说明此时在队列中遇到了第一个null值，然后判断队列剩下的值是否都是null
            }
        }
        //判断队列剩下的值是否都是null，如果存在值不是null的，则不是完全二叉树
        while (!qu.isEmpty()){
            TreeNode pop = qu.poll();
            if(pop != null){
                return false;
            }
        }
        return true;
    }

    /** Oj8 -- 236. 二叉树的最近公共祖先
     给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，
     满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //法1
        if(root == null || p == null || q == null){
            return null;
        }

        Stack<TreeNode> stack1 = new Stack<>();
        getPath(root, p, stack1);
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root, q, stack2);

        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 > size2){
            int size = size1 - size2;
            while(size > 0){
                stack1.pop();
                size--;
            }
        }else{
            int size = size2 - size1;
            while(size > 0){
                stack2.pop();
                size--;
            }
        }
        //两个栈当中 一定是相同的节点个数，此时只需要判断交点
        while(stack1.peek() != stack2.peek()){
            stack1.pop();
            stack2.pop();
        }
        return stack1.peek();
    }
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root == null || node == null){
            return false;
        }
        stack.push(root); //不为空，压栈
        if(root == node){ //找到了
            return true;
        }
        boolean flag1 = getPath(root.left, node, stack);
        if(flag1 == true){
            return true;
        }
        boolean flag2 = getPath(root.right, node, stack);
        if(flag2 == true){
            return true;
        }
        stack.pop(); //如果左右都不是true，将节点出栈
        return false;
    }

    //子问题思路
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){ //法2
        if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor2(root.left, p, q); //在左树找p和q
        TreeNode rightTree = lowestCommonAncestor2(root.right, p, q); //在右树找p和q
        if(leftTree != null && rightTree != null){
            return root;
        }else if(leftTree != null){ //p,q都在左子树上
            return leftTree;
        }else if(rightTree != null){ //p,q都在右子树上
            return rightTree;
        }else{
            return null;
        }
    }

    /** Oj 9 ---- NC64 二叉搜索树与双向链表
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
     */
    TreeNode prev = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        convertChild(pRootOfTree);

        TreeNode head = pRootOfTree;
        while(head.left != null){
            head = head.left;
        }
        return head;
    }
    private void convertChild(TreeNode pCur){
        if(pCur == null){
            return;
        }
        convertChild(pCur.left);
        pCur.left = prev; //null
        if(prev != null){
            prev.right = pCur;
        }
        prev = pCur;
        convertChild(pCur.right);
    }
}
